import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCacheDemo2 {
    //1.定义节点，数据的载体
    class Node<K,V>{
        K key;
        V value;
        Node<K,V> prev;
        Node<K,V> next;

        public Node() {
        }

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

     //2.定义虚拟的双向链表
      class DoubleLinkedList<K,V>{
         Node<K,V> head;
         Node<K,V> tail;

         public DoubleLinkedList() {
             head = new Node<>();
             tail = new Node<>();
             head.next = tail;
             tail.prev = head;
         }

         //3.添加节点
         public void addNode(Node node){
             node.next = head.next;
             node.prev = head;
             head.next.prev = node;
             head.next = node;
         }

         //4.删除节点
         public void deleteNode(Node node){
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.prev = null;
            node.next = null;
         }
         //5.获取最后一个节点
         public Node getLastNode(){
             return tail.prev;
         }
     }




    private int cacheSize;
    Map<Integer,Node<Integer,Integer>> map;
    DoubleLinkedList<Integer,Integer> doubleLinkedList;

    public LRUCacheDemo2(int cacheSize){
        this.cacheSize = cacheSize;
        map = new HashMap<>();
        doubleLinkedList = new DoubleLinkedList();
    }

    public int get(int key){
        if(!map.containsKey(key)){
            return -1;
        }

        Node node = map.get(key);
        doubleLinkedList.deleteNode(node);
        doubleLinkedList.addNode(node);
        return (int) node.value;
    }

    public void put(int key,int value){
        if(map.containsKey(key)){
            Node node = map.get(key);
            node.value = value;
            map.put(key, node);
        }else{
            if(map.size()==cacheSize){
                Node node = doubleLinkedList.getLastNode();
                map.remove(node.key);
                doubleLinkedList.deleteNode(node);
            }
            Node newNode = new Node(key,value);
            map.put(key,newNode);
            doubleLinkedList.addNode(newNode);
        }
    }



    public static void main(String[] args) {
        LRUCacheDemo2 lruCacheDemo = new LRUCacheDemo2(3);

        lruCacheDemo.put(1,1);
        lruCacheDemo.put(2,2);
        lruCacheDemo.put(3,3);
        System.out.println(lruCacheDemo.map.keySet());

        lruCacheDemo.put(4,1);
        System.out.println(lruCacheDemo.map.keySet());

        lruCacheDemo.put(3,1);
        System.out.println(lruCacheDemo.map.keySet());
        lruCacheDemo.put(3,1);
        System.out.println(lruCacheDemo.map.keySet());
        lruCacheDemo.put(3,1);
        System.out.println(lruCacheDemo.map.keySet());
        lruCacheDemo.put(5,1);
        System.out.println(lruCacheDemo.map.keySet());

    }}
